package ljl.alg.wangzheng_camp.round1.twopointers;

import java.util.ArrayList;
import java.util.List;

/**
 * 这个题居然是简单，我毫无头绪
 * */
public class _offer_57_2_continuous_sequence {
    
    /**
     * 和是 target，最少 2 数，则最大 target/2+1 没问题吧？没问题
     * 别用求根公式了，太恶心了
     *
     * 我记着两个指针 i 和 j，这不是双指针吗？
     *
     * 蒙对的不算！
     *
     * */
    public int[][] findContinuousSequence1(int target) {
        List<int[]> res = new ArrayList<>();
        int i = 1, j = 2;
        int sum = 3;
        while (i < j) {
            if (sum < target)
                sum += ++j;
            else if (sum > target)
                sum -= i++;
            else {
                int[] ans = new int[j - i + 1];
                res.add(ans);
                for (int k = i; k <= j; k++) {
                    ans[k - i] = k;
                }
                sum += ++j;
            }
        }
        return res.toArray(new int[0][]);
    }
    
    /**
     * 我没想到暴力解法会这么快？
     * */
    public int[][] findContinuousSequence2(int target) {
        List<int[]> res = new ArrayList<>();
        int sum = 0, limit = (target - 1) / 2;
        for (int i = 1; i <= limit ; i++) {
            for (int j = i;; j++) {
                sum += j;
                if (sum > target) {
                    sum = 0;
                    break;
                } else if (sum == target){
                    int[] ans = new int[j - i + 1];
                    res.add(ans);
                    for (int k = i; k <= j; k++) {
                        ans[k - i] = k;
                    }
                    sum = 0;
                    break;
                }
            }
        }
        return res.toArray(new int[0][]);
    }
    
    /**
     * 求根公式
     * 写一下吧写一下吧
     * (y - x + 1) * (x + y) / 2 = target
     * xy + y2 -x2 - xy + x + y = 2target
     * y2 - x2 + x + y - 2target = 0;
     * y2 + y - (x2 - x + 2target) = 0;
     * δ = (根号下(1 + 4(x2 - x + 2target)) - 1) / 2
     * */
    public int[][] findContinuousSequence3(int target) {
        List<int[]> res = new ArrayList<>();
        int limit = (target - 1) / 2;
        for (int i = 1; i <= limit; i++) {
            double j = ((Math.sqrt(1 + 4 * (long)i * i - 4L * i + 8L * target) - 1) / 2);
            if (j == (int)j && i < j) {
                int[] ans = new int[(int) j - i + 1];
                res.add(ans);
                for (int k = i; k <= j; k++) {
                    ans[k - i] = k;
                }
            }
        }
        return res.toArray(new int[0][]);
    }
}
